#include "tree.h"
#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"
#include <string.h>

//先序遍历 中序遍历 后序遍历 都是相对于根来说的
//把printf注释掉,会发现经过树的路径都是一样的,只是访问结点的时机不同

//先序遍历：先遍历 根 再遍历 左 再遍历 右
//根 左 右
void DLR(BiTNode *root){
        if(root == NULL){
                return;
        }
        printf("%d ", root->data);
        
        //遍历左子树
        DLR(root->lchild);

        //遍历右子树
        DLR(root->rchild);
}
//中序遍历：先遍历 左子树 再遍历 根 再遍历 右子树
// 左 根 右
void LDR(BiTNode *root){
        if(root == NULL){
                return;
        }

        //遍历左子树
        LDR(root->lchild);

        printf("%d ", root->data);

        //遍历右子树
        LDR(root->rchild);
}
//后序遍历：先遍历左子树 再遍历 右子树 再遍历 根
//左 右 根
void LRD(BiTNode *root){
        if(root == NULL){
                return;
        }

        //遍历左子树
        LRD(root->lchild);

        //遍历右子树
        LRD(root->rchild);

        printf("%d ", root->data);
}


//计算二叉树中叶子结点的数目
//采用先序遍历的递归算法
//叶子是左右结点都没有孩子
//if sum++ 无论写在哪个位置都是一样的, 经过树的路径都是一样的,只是访问结点的时机不同
int countLeafNum(BiTree root){
        int sum = 0;
        if(root != NULL){
                if (root->lchild == NULL && root->rchild == NULL){
                        sum++;
                }
                if(root->lchild){
                        sum+=countLeafNum(root->lchild);
                }
                // if (root->lchild == NULL && root->rchild == NULL){
                //         sum++;
                // }
                if(root->rchild){
                        sum+=countLeafNum(root->rchild);
                }
                // if (root->lchild == NULL && root->rchild == NULL){
                //         sum++;
                // }
        }
        return sum;
}

//计算二叉树的深度(高度)
//求出左，右子树的深度 比较大小 谁大 然后+1
int depth(BiTree root){
        int depthLeft = 0;
        int depthRight = 0;
        int depthSum = 0;

        if(root == NULL){
                return depthSum;
        }

        //求左子树的高度
        depthLeft = depth(root->lchild);
        //求右子树的高度
        depthRight = depth(root->rchild);
        //比较大小 谁大 然后+1
        depthSum = 1 + (depthLeft > depthRight ? depthLeft  : depthRight);
        
        return depthSum;
}

//copy一个二叉树
BiTree copyTree(BiTree root){
        BiTNode *newNode = NULL;
        BiTNode *newLp = NULL;
        BiTNode *newRp = NULL;

        if(root == NULL){
                return NULL;
        }

        //拷贝左子树
        if(root->lchild != NULL){
                newLp = copyTree(root->lchild);
        }else{
                newLp = NULL;
        }
        
        //拷贝右子树
        if(root->rchild != NULL){
                newRp = copyTree(root->rchild);
        }else{
                newRp = NULL;
        }

        //malloc根结点
        newNode = (BiTNode *)malloc(sizeof(BiTNode));
        if(newNode == NULL){
                return NULL;
        }
        newNode->lchild = newLp;
        newNode->rchild = newRp;
        newNode->data = root->data;

        return newNode;
}

//中序遍历的非递归方法：先遍历 左子树 再遍历 根 再遍历 右子树 （左 根 右）
//中序遍历的非递归方法需要用到栈的模型 先走的后访问,后走的先访问显然是栈
//1. 有左子树,结点进入栈,没有访问该结点
//2. 有右子树,重复1,
        //没有右子树
                //栈不为空 根据栈顶指示回退 访问栈顶元素 并访问右子树,重复步骤1  
                //栈为空 遍历结束
//一直往左走,找到中序遍历的起点
BiTree goLeft(BiTree node,  LinkStack* stack){
        if(node == NULL){
                return NULL;
        }
        //判断有没有左孩子,没有return
        //如果有入栈,再往左走
        while (node->lchild != NULL){
                LinkStack_Push(stack, node);
                node = node->lchild;       
        }
        return node;
}       

//中序遍历的非递归方法：先遍历 左子树 再遍历 根 再遍历 右子树 （左 根 右）
//中序遍历的非递归方法需要用到栈的模型 先走的后访问,后走的先访问显然是栈
void LDR_NonRecursive(BiTree tree){
        LinkStack* stack = NULL;
        BiTNode* t = NULL;

        stack = LinkStack_Create();
        if(stack == NULL){
                printf("stack create error\n");
                return;
        }

        t = goLeft(tree, stack);
        while (t){
                printf("%d ", t->data);
                //如果t有右子树 重复步骤1
                if(t->rchild != NULL){
                        t = goLeft(t->rchild, stack); //右子树中序遍历的起点
                }else if( LinkStack_Size(stack) >0 ){//没有右子树并且栈不为空 根据栈顶指示回退 访问栈顶元素 并访问右子树,重复步骤1  
                        t = LinkStack_Pop(stack);       
                }else if(LinkStack_Size(stack) == 0){ //有右子树并且栈为空 遍历结束
                        t=NULL;
                        break;
                }
        }
        
}

//创建一个树
//#号补全法 前序遍历创建树
BiTree createBTree(){
        BiTree tree = NULL;
        char ch;
        scanf("%c", &ch);

        if(ch == '#'){
                tree = NULL;
        }else{
                tree = (BiTree)malloc(sizeof(BiTNode));
                memset(tree, 0, sizeof(BiTNode));
                tree->data=ch;
                tree->lchild=createBTree();
                tree->rchild=createBTree();
        }
        return tree;
}

//后序遍历销毁一个树
void BiTree_Free(BiTNode* tree){
        if(tree != NULL){
                if(tree->rchild != NULL) BiTree_Free(tree->rchild);
                if(tree->lchild != NULL) BiTree_Free(tree->lchild);
                if(tree != NULL){
                        free(tree);
                        tree = NULL;
                }
        }
}